<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>&#x5168;&#x6392;&#x5217;</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-body vscode-light">
        <h1 id="全排列">全排列</h1>
<h1 id="1-重复元素不能多次计算-lc-47-permutations-ii">1. 重复元素不能多次计算, LC 47. Permutations II</h1>
<ul>
<li><a href="https://leetcode.com/problems/permutations-ii/">https://leetcode.com/problems/permutations-ii/</a></li>
</ul>
<p>Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.</p>
<pre><code><code><div>Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]


Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
</div></code></code></pre>
<p>我的解法</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">permuteUnique</span>(<span class="hljs-params">self, nums: List[int]</span>) -&gt; List[List[int]]:</span>
        ans = set()
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">helper</span>(<span class="hljs-params">candidates, tmp</span>):</span>
            <span class="hljs-keyword">if</span> len(candidates) == <span class="hljs-number">0</span>:
                ans.add(tuple(tmp))
                <span class="hljs-keyword">return</span>
            n = len(candidates)
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
                helper(candidates[:i]+candidates[i+<span class="hljs-number">1</span>:], tmp+[candidates[i]])
        
        helper(nums, [])
        <span class="hljs-keyword">return</span> list(ans)
</div></code></pre>
<p>官方解法</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">permuteUnique</span>(<span class="hljs-params">self, nums: List[int]</span>) -&gt; List[List[int]]:</span>
        results = []
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">backtrack</span>(<span class="hljs-params">comb, counter</span>):</span>
            <span class="hljs-keyword">if</span> len(comb) == len(nums):
                <span class="hljs-comment"># make a deep copy of the resulting permutation,</span>
                <span class="hljs-comment"># since the permutation would be backtracked later.</span>
                results.append(list(comb))
                <span class="hljs-keyword">return</span>

            <span class="hljs-keyword">for</span> num <span class="hljs-keyword">in</span> counter:
                <span class="hljs-keyword">if</span> counter[num] &gt; <span class="hljs-number">0</span>:
                    <span class="hljs-comment"># add this number into the current combination</span>
                    comb.append(num)
                    counter[num] -= <span class="hljs-number">1</span>
                    <span class="hljs-comment"># continue the exploration</span>
                    backtrack(comb, counter)
                    <span class="hljs-comment"># revert the choice for the next exploration</span>
                    comb.pop()
                    counter[num] += <span class="hljs-number">1</span>

        backtrack([], Counter(nums))

        <span class="hljs-keyword">return</span> results
</div></code></pre>

    </body>
    </html>